package com.wxit.algorithm.tree;

/**
 * 二叉搜索树
 */
public class BSTTree2<T extends Comparable<T>, V> {

    BSTNode<T, V> root;

    static class BSTNode<T, V> {
        T key;
        V value;
        BSTNode<T, V> left;
        BSTNode<T, V> right;


        public BSTNode(T key) {
            this.key = key;
        }

        public BSTNode(T key, V value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(T key, V value, BSTNode<T, V> left, BSTNode<T, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public V get(T key) {
        BSTNode<T,V> p = root;
        while (p != null) {
            int result = key.compareTo(p.key);
            if (result < 0) {
                p = p.left;
            } else if (result > 0) {
                p = p.right;
            } else {
                return p.value;
            }
        }
        return null;
    }

}
